package com.example.demo.tixiban;


/**
 * @author xujm
 * @version V2.4
 *
 *  1-3-5
 *  2-4
 *
 *
 *
 * @since 2.4.0 2022/2/12 11:47
 */
public class List_两个有序链表合并 {


    public static class Node {
        int val;
        Node next;
        Node(int x) { val = x; }
    }

    public static Node merge(Node head1,Node head2,Node head){

        if(head1!=null && head2!=null){

            if(head == null){
                head = head1.val < head2.val ? head1:head2;
            }else{
                head.next =  head1.val < head2.val ? head1:head2;
                head=head.next;
            }
            if(head1.val<head2.val){
                head1=head1.next;
            }else{
                head2=head2.next;
            }
            merge(head1,head2,head);
        }else if(head1!=null){
            if(head == null){
                head = head1;
            }else{
                head.next = head1;
                head=head.next;
            }
            head1=head1.next;
            merge(head1,head2,head);
        }else if(head2!=null){
            if(head == null){
                head = head2;
            }else{
                head.next = head2;
                head=head.next;
            }
            head2=head2.next;
            merge(head1,head2,head);
        }else{
            return head;
        }
        return head;
    }

    public static Node zhengxiang(Node head1,Node head2){
        Node head = null;

        if(head1.val < head2.val){
            head = head1;
            head1 = head1.next;
        }else{
            head = head2;
            head2 = head2.next;
        }
        Node start = head;

        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                head.next = head1;
                head = head.next;
                head1 = head1.next;
            }else{
                head.next = head2;
                head = head.next;
                head2 = head2.next;
            }
        }
        while(head1 != null){
            head.next = head1;
            head = head.next;
            head1 = head1.next;
        }
        while(head2 != null){
            head.next = head2;
            head = head.next;
            head2 = head2.next;
        }
        return start;
    }


    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.next = new Node(3);
        head1.next.next = new Node(5);
        Node head2 = new Node(2);
        head2.next = new Node(4);
        //递归法
        // Node head = merge(head1, head2, null);
        // while(head != null){
        //     System.out.print(head.val+" ");
        //     head=head.next;
        // }
        //正向解法
        Node headx = zhengxiang(head1, head2);
        while(headx != null){
            System.out.print(headx.val+" ");
            headx=headx.next;
        }

    }


}
